﻿//力扣：525. 连续数组
//https://leetcode.cn/problems/contiguous-array/description/


//方法一：暴力法
//时间复杂度O(n^2)
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ret = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum = 0;                                    //注意每轮循环都要将sum置零
            for (int j = i; j < nums.size(); j++)
            {
                sum += nums[j] == 0 ? -1 : 1;           // 将0视为-1，将1视为1，计算子数组和
                if (sum == 0)                           // 如果当前子数组和为0，则说明0和1的数量相同
                {
                    ret = max(ret, j - i + 1);          // 更新最大长度
                }
            }
        }

        return ret;
    }
};






//方法二：前缀和+哈希表
//时间复杂度O(n)

//算法原理：
//稍微转化⼀下题⽬，就会变成我们熟悉的题：
//• 本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。
//• 如果将 0 记为 - 1 ， 1 记为 1 ，问题就变成了找出⼀段区间，这段区间的和等于 0 。
//• 于是，就和 560. 和为 K 的⼦数组 这道题的思路⼀样

//设 i 为数组中的任意位置，⽤ sum[i] 表⽰[0, i] 区间内所有元素的和。
//想知道最⼤的「以 i 为结尾的和为 0 的⼦数组」，就要找到从左往右第⼀个 x1 使得[x1, i]区间内的所有元素的和为 0 。
//那么[0, x1 - 1] 区间内的和是不是就是 sum[i] 了。于是问题就变成：
//• 找到在[0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可。
//我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，第⼀个前缀和等于 sum[i]的位置。
//因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边记录第⼀次出现该前缀和的位置。
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> mp;                     // 哈希表存储前缀和及其索引
        mp[0] = -1;                                     // 初始化前缀和为0的索引为-1

        int ret = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1;               // 将0视为-1，将1视为1，更新前缀和
            if (mp.count(sum))                          // 如果当前前缀和已经存在，计算可能的最大长度
            {
                ret = max(ret, i - mp[sum]);
            }
            else                                        // 如果前缀和不存在，记录当前前缀和及其索引
            {
                mp[sum] = i;
            }
        }

        return ret;
    }
};
//为什么初始化前缀和为 0 的索引为 -1？
//当我们将前缀和为 0 的索引设为 - 1 时，我们便可以更方便地处理从数组开头开始的特殊情况。
//这样可以使代码在遇到从开头的连续子数组（前缀和为 0）时，直接计算出正确的子数组长度。
//
//举例解释
//例如，给定 nums = [0, 1, 0, 1, 1, 0, 0, 1, 1, 1]，目标是找到连续的 0 和 1 数量相等的最长子数组的长度。以下是计算的步骤：
//初始化：sum = 0，mp[0] = -1（表示前缀和为 0 的索引为 - 1）
//遍历数组并计算前缀和：
//索引 0: nums[0] = 0，sum = -1，mp 无 - 1，存储 mp[-1] = 0
//索引 1 : nums[1] = 1，sum = 0，mp 有 0，计算长度 1 - (-1) = 2，更新 ret = 2
//索引 2 : nums[2] = 0，sum = -1，mp 有 - 1，计算长度 2 - 0 = 2，ret 保持为 2
//索引 3 : nums[3] = 1，sum = 0，mp 有 0，计算长度 3 - (-1) = 4，更新 ret = 4
//索引 4 : nums[4] = 1，sum = 1，mp 无 1，存储 mp[1] = 4
//索引 5 : nums[5] = 0，sum = 0，mp 有 0，计算长度 5 - (-1) = 6，更新 ret = 6
//后续计算类似。
//
//总结
//将前缀和 0 的索引初始化为 - 1，使得当前缀和再次为 0 时，可以从数组的开头正确计算长度，从而满足题目要求。
//这是为了确保从头到任意索引的子数组（若符合条件）可以计算出正确的长度。
